package sort;

import java.util.Arrays;
/*
* 希尔排序:就是对插入排序的优化,速度比冒泡,选择,插入排序的速度快,当数组中数据量很大时,
* 希尔排序的速度很快
* 基本思想是:先宏观上对数组进行增量缩进的分组,然后对每次分组后的各个组进行插入排序
* */
public class ShellSort {
    public static void main(String[] args) {
        int[] arr = {101,34,145,25,3,7,15,2,23,4,56,5};

        int index;
        int insertValue;
        /*
        * 1.最外层for循环的作用是对数组进行增量缩进的分组,最开始的分组数为数组元素个数的一半,
        * 每循环一次,分组数都会减少一半,直到最后分组数为1,进行最后一次排序后,整个排序就结束
        * 2.内层for循环就是对分组后各个组的元素进行插入排序
        * */
        for (int gap = arr.length/2; gap > 0 ; gap/=2) {
            for (int i = gap; i < arr.length; i++) {
                index = i-gap;
                insertValue = arr[i];
                while (index>=0 && insertValue<arr[index]) {
                    arr[index+gap]=arr[index];
                    index -= gap;
                }
                arr[index+gap] = insertValue;
            }
        }
        System.out.println(Arrays.toString(arr));
    }
}
